home *** CD-ROM | disk | FTP | other *** search
/ MacHack 2000 / MacHack 2000.toast / pc / The Hacks / Softshoe / Lisa's Portable Parts / Arrays / ArrayHeap.cp < prev    next >
Encoding:
Text File  |  2000-06-23  |  1.5 KB  |  71 lines
  1. // ArrayHeap.cp
  2. #define ArrayHeap_cp
  3.  
  4. #ifndef ArrayHeap_h
  5. #include "ArrayHeap.h"
  6. #endif
  7.  
  8. template < class Element >
  9. ArrayHeap<Element>::ArrayHeap( ArrayOf<Element> array,
  10.                                          Comparison theComparison )
  11.   : heap( array.Start() - 1 ),
  12.      lastElement( array.Length() ),
  13.      compare( theComparison )
  14.   {
  15.     this->MakeHeap();
  16.   }
  17.  
  18. template < class Element >
  19. void ArrayHeap<Element>::Sink( uint32 sinking )
  20.   {
  21.     Assert( sinking > 0 );
  22.     Assert( sinking <= this->lastElement );
  23.     
  24.     Element sinkingElement = this->heap[ sinking ];
  25.     
  26.     while ( 2 * sinking <= this->lastElement )
  27.       {
  28.         uint32 rising = 2 * sinking;
  29.         
  30.         if ( rising < this->lastElement
  31.               && this->compare( this->heap[ rising ], this->heap[ rising+1 ] ) < 0 )
  32.             rising++;
  33.         
  34.         if ( this->compare( sinkingElement, this->heap[ rising ] ) >= 0 )
  35.             break;
  36.         
  37.         this->heap[ sinking ] = this->heap[ rising ];
  38.         sinking = rising;
  39.       }
  40.  
  41.     this->heap[ sinking ] = sinkingElement;
  42.   }
  43.  
  44. template < class Element >
  45. void ArrayHeap<Element>::MakeHeap()
  46.   {
  47.     for ( uint32 i = this->lastElement / 2; i > 0; i-- )
  48.         this->Sink( i );
  49.   }
  50.  
  51. template < class Element >
  52. void ArrayHeap<Element>::Pop()
  53.   {
  54.     Assert( this->lastElement > 0 );
  55.     heap[ 1 ] = this->heap[ this->lastElement-- ];
  56.     if ( this->lastElement > 1 )
  57.         this->Sink( 1 );
  58.   }
  59.  
  60. template < class Element >
  61. void ArrayHeap<Element>::Sort()
  62.   {
  63.     while ( this->lastElement > 1 )
  64.       {
  65.         Element largest = this->Top();
  66.         this->Pop();
  67.         this->heap[ this->lastElement + 1 ] = largest;
  68.       }
  69.     this->lastElement = 0;
  70.   }
  71.